package net.tinkerz.study.algorithms.sort;

import java.util.Random;

/**
 * 归并排序：merge，将两个已经排序好的序列合并成一个序列的操作
 * 归并操作的过程如下：
 *  <ul><li>申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
 * <li>设定两个指针，最初位置分别为两个已经排序序列的起始位置
 * <li>比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
 * <li>重复步骤3直到某一指针达到序列尾
 * <li>将另一序列剩下的所有元素直接复制到合并序列尾
 * 
 * 对于一开始就彻底无序的一个序列，可以使用递归将序列不断缩小，最终子递归中序列只剩两个值时，再调用递归排序<br>
 * 使用递归的好处就是，底层归并完成之后新数组的长度(底层list1+list2)刚好是上层递归的list1或list2的长度
 * </ul>
 * @author zoudongchao
 *
 */
public class MergeSort {
	
	/**
	 * 实现归并排序
	 * @param sorted1		已排序号的数组1
	 * @param sorted1Size	数组1长度
	 * @param sorted2		已排序号的数组2
	 * @param sorted2Size	数组2长度
	 * @return
	 */
	public int[] mergeSort(int[] sorted1, int sorted1Size, int[] sorted2, int sorted2Size) {
		int[] tempStore = new int[sorted1Size+sorted2Size];
		
		int i=0,j=0,k=0;
		//逐个比较 有一个走到结尾就表示比较结束
		while (j < sorted1Size && k < sorted2Size) {
			tempStore[i++] = sorted1[j] < sorted2[k] ? sorted1[j++] : sorted2[k++];//整句结束之后 下表增加
		}
		
		//填充剩余
		while (j < sorted1Size) {
			tempStore[i++] = sorted1[j++];
		}
		while (k < sorted2Size) {
			tempStore[i++] = sorted2[k++];
		}
		
		return tempStore;
	}
	
	/**
	 * divide and conquer<br>
	 * 对输入各取一半，然后递归继续获取，递归完毕之后从最小单元开始进行merge sort
	 * @param source
	 * @return
	 */
	public int[] mergeSort(int[] source) {
		//递归出口
		if (source.length == 1) {
			return source;
		}
		
		int harf = source.length/2;
		
		int[] part1 = new int[harf];
		int[] part2 = new int[source.length-harf];
		
		//Java使用System.arraycopy进行拷贝
		System.arraycopy(source, 0, part1, 0, harf);
		System.arraycopy(source, harf, part2, 0, source.length-harf);
		
		part1 = mergeSort(part1);//处理完成之后 将结果传递至上层  C语言的话直接使用指针就可以了
		part2 = mergeSort(part2);
		
		return mergeSort(part1, harf, part2, source.length-harf);
	}
	
	public static void main(String[] args) {
		MergeSort sort = new MergeSort();
		Random random = new Random();
		
		int[] toSort = new int[20];
		for (int i=0; i<toSort.length; i++) {
			toSort[i] = random.nextInt(40);
			System.out.print(toSort[i]+",");
		}
		System.out.println("");
		toSort = sort.mergeSort(toSort);
		for (int i=0; i<toSort.length; i++) {
			System.out.print(toSort[i]+",");
		}
	}
}
